package com.xiyou.week02.map;

import java.util.HashMap;
import java.util.Map;

/**
 * 697. 数组的度
 *
 * @ClassName：findShortestSubArray
 * @Author：西柚
 * @Date：2022/1/8 6:13 下午
 * @Versiion：1.0
 */
public class FindShortestSubArray {

    /**
     * 输入：nums = [1,2,2,3,1]
     * 输出：2
     * 解释：
     * 输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
     * 连续子数组里面拥有相同度的有如下所示：
     * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
     * 最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。
     *
     * @param nums
     * @return
     */
    public static int findShortestSubArray(int[] nums) {
        // 定义一个Map，Key为数组的值，Value为一个数组，数组的第一个元素为Key的出现次数，第二个元素为Key第一次出现的位置，第三个元素为Key最后一次出现的位置
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        // 遍历数组，将每一个元素出现的次数，第一次出现的位置，最后一次出现的位置记录下来
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            } else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }

        int maxNum = 0;
        int minLen = 0;

        // 遍历Map，寻找出现最多次数的Key，若Key出现的次数相同，则选择长度较短的
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] temp = entry.getValue();
            if (temp[0] > maxNum) {
                maxNum = temp[0];
                minLen = temp[2] - temp[1] + 1;
            } else if (temp[0] == maxNum && minLen > temp[2] - temp[1] + 1) {
                minLen = temp[2] - temp[1] + 1;
            }
        }

        return minLen;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 2, 3, 1};

        System.out.println(findShortestSubArray(nums));
    }

}
